21.Merge Two Sorted Lists

• Linked List, Easy
• introduction
  • 合併兩個升序鏈表，並返回合併後的鏈表頭節點。
• solution
  • 使用 dummy head，逐節點比較兩個鏈表的值，小的接到結果鏈表後移動指標。
  • 時間：O(m+n)
  • 空間：O(1)（直接修改鏈表指標）
• kotlin

class ListNode(var value: Int) {
    var next: ListNode? = null
}

fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
    val dummy = ListNode(0)
    var tail = dummy
    var p1 = l1
    var p2 = l2
    while (p1 != null && p2 != null) {
        if (p1.value < p2.value) {
            tail.next = p1
            p1 = p1.next
        } else {
            tail.next = p2
            p2 = p2.next
        }
        tail = tail.next!!
    }
    tail.next = p1 ?: p2
    return dummy.next
}

• java

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

• python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode()
    tail = dummy
    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

• follow up
  • 如果要合併 k 個已排序鏈表（參考 LeetCode 23）該怎麼做？
    • 合併 k 個已排序鏈表（LeetCode 23）
      • 方法 1（逐一合併）：每次合併兩個 → 時間 O(kN)
        -方法 2（分治合併）：每次合併成對鏈表 → 時間 O(N log k)
      • 方法 3（優先佇列/最小堆）：用 Min Heap 取最小節點 → 時間 O(N log k)
  • 如果鏈表非常大，如何優化空間？
    • 使用迭代而非遞迴，避免深度遞迴棧溢出
    • 若在外部存儲（如磁碟）上，可考慮流式處理（Streaming Merge）
  • 能否用遞迴解法實現？
    • 可以（上方遞迴版範例）
    • 注意 Kotlin 遞迴不是尾遞迴優化的，鏈表長度過大可能導致 StackOverflow